package twobranchTree.connectright;
/**
 * @Date 2020/03/03
 * @author 王光浩
 * @Thinkging 使用类似与morris遍历的方法进行（但是采用的是递归）。
 * 复杂度分析：时间复杂度O（2n），空间复杂度O（1）——除去栈空间
 */
public class MyMethodOne {
	public Node connect(Node node) {
		if(node==null)return null;
		recursively(node);
		return node;
	}
	private void recursively(Node root) {
		if(root.left==null)return;  //该节点为叶子节点
		root.left.next=root.right;  //将该节点的左右子节点进行连接
		//将root节点的左右子树进行连接
		Node leftNode=root.left.right;
		Node rightNode=root.right.left;
		while(leftNode!=null && rightNode!=null) {
			leftNode.next=rightNode;
			leftNode=leftNode.right;
			rightNode=rightNode.left;
		}
		recursively(root.left);
		recursively(root.right);
	}
}
